package Learn;

public class Find178 {

    //分块查找
    //每一块的最大值存储到一个信息表（数组）
    public static void main(String[] args) {
//        int[] arr = {16, 5, 9, 12, 21, 18,
//                32, 23, 37, 26, 45, 34,
//                50, 48, 61, 52, 73, 65};
//
//
//        //分块 总数开根号 大概是这么多块 可以调整
//
//        //创建块数对象
//
//        Block b1 = new Block(21, 0, 5);
//        Block b2 = new Block(45, 6, 11);
//        Block b3 = new Block(73, 12, 17);
//
//        Block[] arr1 = {b1, b2, b3};
//
//        int number = 65;
//        int index = getIndex(arr1, arr, number);
//        System.out.println(index);

        //分块拓展
//        int[]arr={27,22,30,40,36,
//        13,19,16,20,
//        7,10,
//        43,50,48};
//
//        Block1 b1=new Block1(22,40,0,4);
//        Block1 b2=new Block1(13,20,5,8);
//        Block1 b3=new Block1(7,10,9,10);
//        Block1 b4=new Block1(43,50,11,13);
//        Block1[] arr1={b1,b2,b3,b4};
//
//        int number=43;
//        int index1 = getIndex1(arr1, arr, number);
//        System.out.println(index1);


        //哈希查找 分几块 然后挂

    }

    public static int getIndex(Block[] arr1, int[] arr, int a) {
        int start = 0;
        int end = 0;
        for (int i = 0; i < arr1.length; i++) {
            if (a <= arr1[i].getMax()) {
                start = arr1[i].getStart();
                end = arr1[i].getEnd();
                break;
            }
        }
        for (int i = start; i <= end; i++) {
            if (arr[i] == a) {
                return i;
            }
        }
        return -1;
    }

    public static int getIndex1(Block1[] arr1, int[] arr, int a) {
        int start=0;
        int end=0;
        for (int i = 0; i < arr1.length; i++) {
            if(a>=arr1[i].getMin()&&a<=arr1[i].getMax()){
                start = arr1[i].getStart();
                end=arr1[i].getEnd();
            }
        }
        for (int i = start; i <=end; i++) {
            if(arr[i]==a){
                return i;
            }
        }
        return -1;
    }
}

class Block {
    private int max;
    private int start;
    private int end;


    public Block() {
    }

    public Block(int max, int start, int end) {
        this.max = max;
        this.start = start;
        this.end = end;
    }

    /**
     * 获取
     *
     * @return max
     */
    public int getMax() {
        return max;
    }

    /**
     * 设置
     *
     * @param max
     */
    public void setMax(int max) {
        this.max = max;
    }

    /**
     * 获取
     *
     * @return start
     */
    public int getStart() {
        return start;
    }

    /**
     * 设置
     *
     * @param start
     */
    public void setStart(int start) {
        this.start = start;
    }

    /**
     * 获取
     *
     * @return end
     */
    public int getEnd() {
        return end;
    }

    /**
     * 设置
     *
     * @param end
     */
    public void setEnd(int end) {
        this.end = end;
    }

    public String toString() {
        return "Block{max = " + max + ", start = " + start + ", end = " + end + "}";
    }
}
class Block1{
    private int min;
    private int max;
    private int start;
    private int end;


    public Block1() {
    }

    public Block1(int min, int max, int start, int end) {
        this.min = min;
        this.max = max;
        this.start = start;
        this.end = end;
    }

    /**
     * 获取
     * @return min
     */
    public int getMin() {
        return min;
    }

    /**
     * 设置
     * @param min
     */
    public void setMin(int min) {
        this.min = min;
    }

    /**
     * 获取
     * @return max
     */
    public int getMax() {
        return max;
    }

    /**
     * 设置
     * @param max
     */
    public void setMax(int max) {
        this.max = max;
    }

    /**
     * 获取
     * @return start
     */
    public int getStart() {
        return start;
    }

    /**
     * 设置
     * @param start
     */
    public void setStart(int start) {
        this.start = start;
    }

    /**
     * 获取
     * @return end
     */
    public int getEnd() {
        return end;
    }

    /**
     * 设置
     * @param end
     */
    public void setEnd(int end) {
        this.end = end;
    }

    public String toString() {
        return "Block1{min = " + min + ", max = " + max + ", start = " + start + ", end = " + end + "}";
    }
}



